<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>插入排序</title>
    <style>
      body {
        margin-left: 20px;
      }
    </style>
  </head>

  <body>
    <div>
      <p>1. 从第一个元素开始，该元素可以认为已经被排序</p>
      <p>2.取出下一个元素，在已经排序的元素序列中从后向前扫描</p>
      <p>3.如果该元素（已排序）大于新元素，将该元素移到下一位置</p>
      <p>4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置</p>
      <p>5. 将新元素插入到该位置后</p>
      <p>6. 重复步骤 2~5</p>
    </div>
    <script>
      // function insertionSort(arr) {
      //   const res = []
      //   for (let i in arr) {
      //     let maxIndex = i
      //     if (res.length < 1) {
      //       res.push(arr[i])
      //     } else {
      //       for (let j = res.length - 1; j > -1; j--) {
      //         if (res[j] > arr[i]) {
      //           maxIndex = j
      //         }
      //       }
      //       res.splice(maxIndex, 0, arr[i])
      //     }
      //   }
      //   return res
      // }

      function insertionSort(array) {
        var length = array.length,
          i,
          j,
          temp
        for (i = 1; i < length; i++) {
          temp = array[i]
          for (j = i; j >= 0; j--) {
            if (array[j - 1] > temp) {
              array[j] = array[j - 1]
            } else {
              array[j] = temp
              break
            }
          }
        }
        return array
      }

      console.log(insertionSort([5, 1, 4, 2, 3, 8]))
    </script>
  </body>
</html>
